package company.dynamic;

import java.util.Scanner;

/**
 * 96. 不同的二叉搜索树
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 *
 * 输入：n = 3
 * 输出：5
 *
 * 输入：n = 3
 * 输出：5
 *
 * 分析： 构建2叉树方案=f（i， n）的累加，就是选中i作为根节点情况下，1-i的组合累加
 举例而言，创建以
 3
 3 为根、长度为
 7
 7 的不同二叉搜索树，整个序列是
 [1,2,3,4,5,6,7]我们需要从左子序列
 [1,2] 构建左子树，从右子序列[4,5,6,7] 构建右子树，然后将它们组合（即笛卡尔积）。
 对于这个例子，不同二叉搜索树的个数为F(3,7)。我们将[1,2]构建不同左子树的数量表示为
 G(2), 从[4,5,6,7]
 构建不同右子树的数量表示为G(4)，注意到
 G(n) 和序列的内容无关，只和序列的长度有关。于是
 在1，2，3，4，5，6，7 中选3为根节点，方案数等于1-3和3-7两段左右子树构建的方案数组合
 F(3,7)=G(2)⋅G(4)。 因此，我们可以得到以下公式：F(i,n)=G(i−1)⋅G(n−i)
 */
public class NumTrees96 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(numTrees(n));
    }
    public static int numTrees(int n) {
        int[] dp = new int [n+1];
        // 注意没树的时候，方案也是1
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                // 分别从1-i 选择根节点，也就是在i个数字时候，有多少种方案
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
